Search results for "equivalence closure"

showing 1 items of 1 documents

Equivalence closure in the two-variable guarded fragment

2015

We consider the satisfiability and finite satisfiability problems for the extension of the two-variable guarded fragment in which an equivalence closure operator can be applied to two distinguished binary predicates. We show that the satisfiability and finite satisfiability problems for this logic are 2-ExpTime-complete. This contrasts with an earlier result that the corresponding problems for the full two-variable logic with equivalence closures of two binary predicates are 2-NExpTime-complete.

Computational complexity theoryLogiccomputational complexityguarded fragmentsatisfiability problemBinary numberTheoretical Computer ScienceCombinatoricsArts and Humanities (miscellaneous)Computer Science::Logic in Computer ScienceClosure operatorEquivalence (formal languages)MathematicsDiscrete mathematicssatisfiability problemcomputational complexitydecidabilityequivalence closureSatisfiabilityDecidabilityTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESClosure (computer programming)Hardware and ArchitectureTheoryofComputation_LOGICSANDMEANINGSOFPROGRAMSBoolean satisfiability problemSoftwareJournal of Logic and Computation
researchProduct